package 公司真题.携程;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;

public class _LURCACHE {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int capacity = Integer.parseInt(sc.nextLine());
        if (capacity == 0) {
            while (sc.hasNextLine()) {
                String str = sc.nextLine().trim();
                String[] strArr = str.split(" ");
                if (strArr.length == 2) {
                    System.out.println(-1);
                } else {

                }
            }
            System.exit(0);
        }
        LRU lru = new LRU(capacity);
        while (sc.hasNextLine()) {
            String str = sc.nextLine().trim();
            String[] strArr = str.split(" ");
            if (strArr.length == 2) {
                // get操作
                System.out.println(lru.get(strArr[1]));
            } else {
                // put操作
                lru.put(strArr[1],strArr[2]);
            }
        }
    }


}
class LRU {

    private int capacity;

    private Node head = new Node();

    private Node tail = new Node();

    public Map<String, Node> map = new HashMap<>();

    public LRU(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public void put(String key, String value) {
        if (map.get(key) != null) {
            // 更新值
            map.get(key).value = value;
        } else {
            // 插入值
            if (ensureCapacity()) {
                // 没有超出容量
                // 那就把这个新的node节点插入到head的下一个
                Node node = new Node();
                node.key = key;
                node.value = value;
                head.next.prev = node;
                node.next = head.next;
                head.next = node;
                node.prev = head;
                map.put(key,node);
            } else {
                // 超出了容量,先删除最后一个节点
                Node lastNode = map.get(tail.prev.key);
                lastNode.prev.next = tail;
                tail.prev = lastNode.prev;
                map.remove(lastNode.key);

                // 然后再添加新节点
                Node node = new Node();
                node.key = key;
                node.value = value;
                head.next.prev = node;
                node.next = head.next;
                head.next = node;
                node.prev = head;
                map.put(key,node);
            }
        }
    }

    public int get(String key) {
        if (map.get(key) == null) {
            return -1;
        } else {
            // 先把这个节点移动到head的下一个
            Node node = map.get(key);
            node.next.prev = node.prev;
            node.prev.next = node.next;

            head.next.prev = node;
            node.next = head.next;
            head.next = node;
            node.prev = head;

            return Integer.parseInt(map.get(key).value);
        }
    }

    private boolean ensureCapacity() {
        return (map.size() + 1) <= capacity;
    }

    private static class Node{
        String key;
        String value;
        Node prev;
        Node next;
        public Node() {

        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return Objects.equals(key, node.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }
    }
}